//Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] 
//< nums[3].... 
//
// You may assume the input array always has a valid answer. 
//
// 
// Example 1: 
//
// 
//Input: nums = [1,5,1,1,6,4]
//Output: [1,6,1,5,1,4]
//Explanation: [1,4,1,5,1,6] is also accepted.
// 
//
// Example 2: 
//
// 
//Input: nums = [1,3,2,2,3,1]
//Output: [2,3,1,3,1,2]
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5 * 104 
// 0 <= nums[i] <= 5000 
// It is guaranteed that there will be an answer for the given input nums. 
// 
//
// 
//Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space? R
//elated Topics 数组 分治 快速选择 排序 
// 👍 312 👎 0


package leetcode.editor.cn;

//Java：Wiggle Sort II
public class P324WiggleSortIi {
    public static void main(String[] args) {
        Solution solution = new P324WiggleSortIi().new Solution();
        solution.wiggleSort(new int[]{1, 5, 1, 1, 6, 4});
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void wiggleSort(int[] nums) {
            int[] bucket = new int[5001];
            for (int num : nums) {
                bucket[num]++;
            }
            int len = nums.length;
            int small, big;//穿插数字时的上界
            //总长度为奇数时，“小 大 小 大 小”边界左右都为较小的数；
            //总长度为偶数时，“小 大 小 大”边界左为较小的数，边界右为较大的数
            if ((len & 1) == 1) {
                small = len - 1;
                big = len - 2;
            } else {
                small = len - 2;
                big = len - 1;
            }
            int j = 5000; //从后往前，将桶中数字穿插到数组中，后界为j
            //桶中大的数字在后面，小的数字在前面，所以先取出较大的数字，再取出较小的数字
            //先将桶中的较大的数字穿插放在nums中
            for (int i = 1; i <= big; i += 2) {
                while (bucket[j] == 0) {
                    j--;//找到不为0的桶
                }
                nums[i] = j;
                bucket[j]--;
            }
            //再将桶中的较小的数字穿插放在nums中
            for (int i = 0; i <= small; i += 2) {
                while (bucket[j] == 0) {
                    j--;//找到不为0的桶
                }
                nums[i] = j;
                bucket[j]--;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}